package com.yang.Dp.HouseRobber;

import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yang
 * @Description: 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
 * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
 * 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
 * @Date: Created in 17:21 2022/8/12
 * @Modified By:
 */
public class HouseRobber3 {
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class HouseRobber3Solution {

    // 记忆化递推
/*    Map<TreeNode, Integer> map;
    public int rob(TreeNode root) {
        // 如果node偷 那么node.left||node.right 就不能偷
        // 然后下一步偷node的左右孙子
        // 如果node不偷，那么 下一步偷node的左右孩子
        if(root == null){
            return 0;
        }
        map = new HashMap<>();;
        return dfs(root);
    }

    int dfs(TreeNode node){
        if(node == null){
            return 0;
        }
        if(node.left == null && node.right == null){
            return node.val;
        }
        if(map.containsKey(node)){
            return map.get(node);
        }
        // 如果偷头结点
        int val1 = node.val;
        if(node.left != null) val1 += dfs(node.left.right) + dfs(node.left.left);
        if(node.right != null) val1 += dfs(node.right.right) + dfs(node.right.left);

        int val2 = dfs(node.left) + dfs(node.right);
        map.put(node, Math.max(val1, val2));
        return Math.max(val1, val2);
    }*/
}
